package LeetCode._02算法基础.day18动态规划;

/**
 * @author 挚爱之夕
 * @version 困难
 * @implSpec 给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 * 输入：word1 = "horse", word2 = "ros"
 * 输出：3
 * 解释：
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 *
 * @since 2022 - 09 - 14 - 15:20
 */
public class _72编辑距离 {
    public static void main(String[] args) {
        String word1 = "horse", word2 = "ros";
        System.out.println(minDistance(word1, word2));
    }
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if(m * n == 0)
            return m + n;
        //dp[i][j] 表示 word1 前i（从1开始）个字符 和 word2 前i（从1开始）个字符的最小编辑距离
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        for(int i = 0; i <= m; i++) dp[i][0] = i;   //word2 空 删除 i 次
        for(int j = 0; j <= n; j++) dp[0][j] = j;   //word1 空 插入 i 次

        //三种情况
        int t1, t2, t3;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                t1 = dp[i - 1][j] + 1;  //word1[1,i-1]末尾 添加 word2.charAt(j - 1)
                t2 = dp[i][j - 1] + 1;  //word1[1,i]末尾 删除
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){ //这两个位置字符相同
                    t3 = dp[i - 1][j - 1];
                }else{  //执行一次替换
                    t3 = dp[i - 1][j - 1] + 1;
                }
                //取最小操作次数
                dp[i][j] = Math.min(t1, Math.min(t2, t3));
            }
        }
        return dp[m][n];
    }
}
